package chapter02;

import java.util.HashMap;
import java.util.HashSet;

public class IsScramble87 {
    /**
     * 记忆化搜索
     * 判断s1经过扰乱能否得到s2
     * process(i,j,length) s1从下标i、s2从下标j开始后面长度length个字符能否构成扰乱字符串
     * 在判断前可以先排除一些情况
     * 1).s1和s2长度不同
     * 2).s1的字串和s2的字串字符种类和数量不同
     * 满足以上情况进行递归判断
     * 假设s1从下标i s2从下标j 判断后面length个字符能否构成扰乱字符串
     * 遍历每个长度pos->[1,length) 分割后不能有空字串
     *   1).s1前部分和s2前部分可能构成扰乱字符串&&s1后部分和s2后部分可能构成扰乱字符串
     *      (i,j,pos)&&(i+pos,j+pos,length-pos)
     *   2).s1前部分和s2后部分可能构成扰乱字符串&&s1后部分和s2前部分可能构成扰乱字符串
     *      (i,j+length-pos,pos)&&(i+pos,j,length-pos)
     * 为了避免重复递归 增加缓冲数组dp[i][j][length]
     * 初始化为0 可以构成扰乱字符串返回1 不可以构成扰乱字符串返回-1
     */
    public boolean isScramble(String s1, String s2) {
        if(s1.length()!=s2.length()){
            return false;
        }
        if(s1.equals(s2)) {
            return true;
        }
        int length=s1.length();
        int[][][] dp=new int[length][length][length+1];
        return process(s1,s2,0,0,length,dp);
    }

    public boolean process(String s1,String s2,int i,int j,int length,int[][][] dp){
        if(dp[i][j][length]!=0){
            return dp[i][j][length]==1;
        }
        String a=s1.substring(i,i+length);
        String b=s2.substring(j,j+length);
        if(a.equals(b)){
            dp[i][j][length]=1;
            return true;
        }
        if(!check(a,b)){
            dp[i][j][length]=-1;
            return false;
        }
        for(int pos=1;pos<length;pos++){
            if(process(s1,s2,i,j,pos,dp)&&process(s1,s2,i+pos,j+pos,length-pos,dp)){
                dp[i][j][length]=1;
                return true;
            }
            if(process(s1,s2,i,j+length-pos,pos,dp)&&process(s1,s2,i+pos,j,length-pos,dp)){
                dp[i][j][length]=1;
                return true;
            }
        }
        dp[i][j][length]=-1;
        return false;
    }

    public boolean check(String s1,String s2){
        if(s1.length()!=s2.length()){
            return false;
        }
        int[] charCount1=new int[26];
        int[] charCount2=new int[26];
        char[] chs1=s1.toCharArray();
        char[] chs2=s2.toCharArray();
        int length=s1.length();
        for(int i=0;i<length;i++){
            charCount1[chs1[i]-'a']++;
            charCount2[chs2[i]-'a']++;
        }
        for(int i=0;i<26;i++){
            if(charCount1[i]!=charCount2[i]){
                return false;
            }
        }
        return true;
    }

}
